Laying out objects for a document is a well-known problem. A layout technique called SmartNails allowed scaling, cropping and re-positioning of document image objects that were laid out originally on one page. Given display size constraints, an optimization is performed to reposition the document image objects using a greedy algorithm. For more information, see U.S. Pat. No. 7,272,258, entitled “Reformatting Documents Using Document Analysis Information,” filed Jan. 29, 2003, and U.S. Pat. No. 7,177,488, entitled “Resolution Sensitive Layout of Document Regions,” filed May 9, 2003, both assigned to the corporate assignee of the present invention.
Genetic algorithms have been applied to the document layout problem. In one case, an optimization framework of combinatoric nature is used to optimize aesthetic criteria of a layout, given rectangles positioned on a page and attributes created by the user or an application. In this case, the aesthetic criteria include alignment, balance, uniformity, white-space fraction, white-space free-flow, regularity, page security and aspect ratio. Costs are defined for each of these criteria. A combined cost is defined as a weighted sum of the individual costs. However, content of the image objects does not influence the aesthetic measures. A user or some application program initially places a set of non-overlapping rectangles. Then the optimization achieves an adjustment of the positioning of the rectangles following the aesthetic measures. For more information, see U.S. Pat. No. 7,035,438, entitled “System and method for measuring and quantizing document quality,” published Feb. 3, 2005; U.S. Pat. No. 7,171,617, entitled “System and method for fitness evaluation for optimization in document assembly,” published Feb. 5, 2004; and U.S. Pat. No. 7,487,445, entitled “Constraint-optimization system and method for document component layout generation,” published Jan. 29, 2004.
In another approach, an existing formatted document page is taken, i.e. the layout is already represented, and the user is allowed to add more text to a text object or to reformat the page for a different size paper (from letter to A4). Thus, the original layout does not change very much, but is merely “adjusted.” The optimization problem is formulated as a linear cost function with linear constraints and is solved using constraint solving software from the University of Washington. For more information, see Lin, X. (HP Labs), “Active Document Layout Synthesis,” Proc. ICDAR 2005, Seoul, South Korea, pg. 86-90.
In yet another approach, a system takes an initial set of rectangles (containers) that need to be filled with content in which the positions of the initial rectangles (containers) are chosen first and cannot be altered. Then the content is fitted. The content is described as being image, graphic, text or a combination of the three. For more information, see U.S. Pat. No. 7,203,902, entitled “Document Composition,” published Apr. 7, 2005.
U.S. Pat. No. 6,173,286, entitled “Computer-implemented optimization of publication layouts,” filed Jan. 9, 2001, discloses a method that starts with a given layout representation similar to the containers described above. Then an optimization algorithm fills the containers with document objects from a data base. A cost is calculated for each object selection. The set of objects with minimal cost are finally placed. For the optimization of the filling of the containers, a biological programming model is used (evolution or genetic algorithm). The to-be-placed objects carry attributes that are used in the optimization step. They are compared to unspecified attributes of the layout.